import java.util.BitSet;

/**
 * @author gao
 * @date 2025/9/9 15:15
 */

class SimpleHash {
    public int cap; // 当前容量
    public int seed; // 随机数

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

/**
 * 计算字符串key的哈希值，用于确定在数组中的存储位置
 * @param key 需要计算哈希值的字符串
 * @return 计算后的哈希值
 */
    int hash(String key) {
        int h;
        // （n - 1） & hash找到数组下标
        // 将key的hashCode与自身右移16位后的结果进行异或运算，增加哈希的随机性
        return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
}

public class MyBloomFilter {
    // 布隆过滤器的大小
    public static final int DEFAULT_SIZE = 1 << 20;
    public BitSet bitSet; //位图
    public int usedSize; // 已使用的位数
    public static final int[] seeds = {5, 7, 11, 13, 27, 33};
    public SimpleHash[] simpleHashes;

    // 初始化伪数组大小和哈希函数数组
    public MyBloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[seeds.length];
        for (int i = 0; i < seeds.length; i++) {
            simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

/**
 * 向布隆过滤器中添加元素
 * @param val 需要添加的元素
 */
public void add(String val) {
    // 让多个哈希函数分别处理当前数据
    for (SimpleHash simpleHash : simpleHashes) {
        int index = simpleHash.hash(val);
        // 将对应位置的bit设置为1
        bitSet.set(index);
    }
}

    /**
     * 判断布隆过滤器中是否包含指定元素，存在一定误判性
     * @param val 需要判断的元素
     * @return 如果包含返回true，否则返回false
     */
    public boolean contains(String val) {
        if (val == null) {
            return false;
        }
        // 让多个哈希函数分别处理当前数据
        for (SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            // 如果有一个位置的bit为0，则说明该元素一定不存在
            if (!bitSet.get(index)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("Baidu");
        myBloomFilter.add("Google");
        myBloomFilter.add("bytedance");
        myBloomFilter.add("Facebook");
        myBloomFilter.add("YouTube");
        myBloomFilter.add("Tencent");

        System.out.println(myBloomFilter.contains("Baidu"));
        System.out.println(myBloomFilter.contains("MicroSoft"));
    }
}